#lang sicp

(define (square x) (* x x))

(define (halve x) (quotient x 2))

(define (expmod base exp mod)
  (cond ((= exp 0) 1)
        ((= base 1) 0)
        ((even? exp) (expmod (square base) (halve exp) mod))
        (else (remainder (* base (expmod (square base) (halve exp) mod)) mod))))

(define (random-in-range l r)
  (+ (random (+ (- r l) 1)) l))

(define (Miller-Rabin-test n)
  (define (check x)
    (= (expmod x (- n 1) n) 1))
  (check (random-in-range 2 (- n 2))))

(define (prime? n times)
  (if (= times 0)
      #t
      (and (Miller-Rabin-test n)
           (prime? n (- times 1)))))